package com.maixy.dailydemo.algorithm;

/**
 * @ClassName Test52
 * @Description 在排序数组中查找数字 I
 * 统计一个数字在排序数组中出现的次数。
 * （这一题使用二分法,不然太简单了,才能符合考点）
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0
 * m 0 2 4 5
 * i 0 3 5 5
 * j 5 5 5 4
 * right 5
 *
 * m 5 2 4 3
 * i 0 3 3 3
 * j 5 5 3 2
 * left 2
 * @Date 2021/4/28 9:59
 * @Author maixy
 */
public class Test52 {
    public int search(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        // 若数组中无 target ，则提前返回
        if(j >= 0 && nums[j] != target) return 0;
        // 搜索左边界 left
        i = 0; j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }
}
